package 克鲁斯卡尔Kruskal算法;

import java.util.Arrays;
import java.util.Comparator;

public class 克鲁斯卡尔算法 {

	public static void main(String[] args) {
		//克鲁斯卡尔Kruskal，求最小生成树，从最小边开始
		
		char[] vertexs = {'A','B','C','D','E','F','G'};
		//极大值，不连通
		final int N = Integer.MAX_VALUE;
		int[][] matrix = {
				{0 ,12,N ,N ,N ,16,14},
				{12,0 ,10,N ,N ,7 ,14},
				{N ,10,0 ,3 ,5 ,6 ,N },
				{N ,N ,3 ,0 ,4 ,N ,N },
				{N ,N ,5 ,4 ,0 ,2 ,8 },
				{16,7 ,6 ,N ,2 ,0 ,9 },
				{14,N ,N ,N ,8 ,9 ,0 },
		};
		Kruskal kruskal = new Kruskal(vertexs, matrix);
		kruskal.show();
		kruskal.kruskal();
	}
	
	
}
/**
 * 克鲁斯卡尔算法
 * @author PC
 *
 */
class Kruskal {
	
	//边的个数
	int edgeNum;
	//顶点数组
	char vertexs[];
	//邻接矩阵
	int matrix[][];
	//极大值，不连通
	static final int N = Integer.MAX_VALUE;
	
	/**
	 * 构造器，初始化顶点，临街矩阵，可以直接赋值，也可以用拷贝的方式，这样不会修改原来数组的值
	 * 因为数组方式的引用赋值，一旦修改就会改变原数组的值
	 * @param vertexs 顶点数组
	 * @param matrix 邻接矩阵
	 */
	public Kruskal(char[] vertexs, int[][] matrix) {
		
		//初始化顶点个数和边个数，

		//获取数组长度，用于初始化邻接表
		int vlen = vertexs.length;
		
		//初始化顶点数组，使用拷贝方式
		this.vertexs = new char[vlen];
		for (int i = 0; i < vertexs.length; i++) {
			this.vertexs[i] = vertexs[i]; 
		}
		
		//初始化邻接矩阵，使用拷贝方式
		this.matrix = new int[vlen][vlen];
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				this.matrix[i][j] = matrix[i][j];
			}
		}
		
		//统计边的条数，就是邻接矩阵中有值的点，但是邻接矩阵是重复的 （A，B）与（B，A）同
		//所以只算半边矩阵，也可以在上面的循环中遍历
		//int j = i + 1 ;从 i 的上半个三角算
		for (int i = 0; i < vlen; i++) {
			for (int j = i+1; j < vlen; j++) {
				if(this.matrix[i][j] != N) {
					edgeNum++;
				}
			}
		}
	}
	
	
	//克鲁斯卡尔算法
	public void kruskal() {
		//1. 记录结果数组的索引
		int index = 0;
		//2. 记录“已有最小生成树”中每个顶点在最小生成树的终点，顶点之间的关系，在并查集中有讲
		int ends[] = new int[vertexs.length];
		//3. 记录最小生成树结果的数组，共有n-1个结果
		EData rets[] = new EData[vertexs.length-1];
		
		//4. 获取图中 所有的边
		EData edges[] = getEdges();
		//5. 对边参照权值进行排序小-大
		sort(edges);
		
		//6. 遍历edges数组，查找合适的边添加到最小生成树，判断是否回路，无则加
		for (int i = 0; i < edges.length; i++) {
			//获取第i条边的两个顶点
			int p1 = getPosition(edges[i].start);
			int p2 = getPosition(edges[i].end);
			//获取这两个顶点的根
			int r1 = getEnd(ends, p1);
			int r2 = getEnd(ends, p2);
			//判断是否回路
			if(r1 != r2) {
				//无回路，加入结果
				rets[index++] = edges[i];
				//并将一方结点放入另一结点下
				ends[r1] = r2;
			}
		}
		
		//打印最小生成树
		for (int i = 0; i < rets.length; i++) {
			System.out.println(rets[i]);
		}
		
	}
	
	
	
	/**
	 * 排序
	 * @param edatas
	 */
	public void sort(EData[] edatas) {
		Arrays.sort(edatas);
	}

	/**
	 * 获取字符对应下标 'A'=0; 'B'=1
	 * @param c
	 * @return
	 */
	public int getPosition(char c) {
		for (int i = 0; i < vertexs.length; i++) {
			if(vertexs[i] == c) {
				return i;
			}
		}
		//没找到
		return -1;
	}
	
	/**
	 * 获取图中的边，放进数组，后面会用到，排序之后再使用
	 * 利用邻接矩阵matrix，
	 * @return EData('A','B',1)形式
	 */
	public EData[] getEdges() {
		
		//计数，index记录EData数组
		int index = 0;
		//数组，存边
		EData edges[] = new EData[edgeNum];
		//循环matrix邻接矩阵，此处仍用 int j = i + 1，只取上三角，去重
		for (int i = 0; i < matrix.length; i++) {
			for (int j = i+1; j < matrix[i].length; j++) {
				if(matrix[i][j] != N) {
					//注意：(vertexs[i], vertexs[j], matrix[i][j])，前两个是vertexs数组char类型
					edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
				}
			}
		}
		return edges;
	}
	
	/**
	 * 并查集
	 * 利用ends关系表查找，i顶点的根
	 * @param ends 关系表，动态创建
	 * @param i
	 * @return
	 */
	public int getEnd(int ends[], int i) {
	
		while(ends[i] != 0) {
			i = ends[i];
		}
		return i;
	}
	
	
	/**
	 * 打印邻接矩阵
	 */
	public void show() {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				System.out.print(matrix[i][j] + "\t");
			}
			System.out.println();
		}
	}
	
}

/**
 * 边
 * 有两个顶点，和权值，和实现了Comparable可进行排序Collections.sort/Arrays.sort
 * @author PC
 *
 */
class EData implements Comparable<EData>{
	//一个顶点
	char start;
	//一个顶点
	char end;
	//权值
	int weight;
	
	public EData(char start, char end, int weight) {
		super();
		this.start = start;
		this.end = end;
		this.weight = weight;
	}
	@Override
	public String toString() {
		return "EData [start=" + start + ", end=" + end + ", weight=" + weight + "]";
	}
	//排序，比较器
	@Override
	public int compareTo(EData o) {
		return this.weight - o.weight;
	}
	
	
}